package class21;

/**
 * @author YZY
 * @since 2022/8/21 14:39
 * 给定一个二维数组matrix，一个人必须从左上角出发，最后到达右下角
 * 沿途只可以向下或者向右走，沿途的数字都累加就是距离累加和
 * 返回最小距离累加和
 */
public class Code01_MinPathSum {

    /**
     * 暴力尝试
     */
    public static int minPathSum1(int[][] matrix) {
        return process1(matrix, matrix.length - 1, matrix[0].length - 1);
    }

    private static int process1(int[][] matrix, int x, int y) {
        if (x == 0 && y == 0) {
            return matrix[x][y];
        }
        if (x == 0) {
            return process1(matrix, x, y - 1) + matrix[x][y];
        }
        if (y == 0) {
            return process1(matrix, x - 1, y) + matrix[x][y];
        }
        int p1 = process1(matrix, x - 1, y);
        int p2 = process1(matrix, x, y - 1);
        return Math.min(p1, p2) + matrix[x][y];
    }

    /**
     * 记忆化搜索
     */
    public static int minPathSum2(int[][] matrix) {
        int[][] dp = new int[matrix.length][matrix[0].length];
        return process2(matrix, matrix.length - 1, matrix[0].length - 1, dp);
    }

    private static int process2(int[][] matrix, int x, int y, int[][] dp) {
        if (x == 0 && y == 0) {
            return matrix[x][y];
        }
        if (dp[x][y] != 0) {
            return dp[x][y];
        }
        if (x == 0) {
            return process2(matrix, x, y - 1, dp) + matrix[x][y];
        }
        if (y == 0) {
            return process2(matrix, x - 1, y, dp) + matrix[x][y];
        }
        int p1 = process2(matrix, x - 1, y, dp);
        int p2 = process2(matrix, x, y - 1, dp);
        return dp[x][y] = Math.min(p1, p2) + matrix[x][y];
    }

    /**
     * 动态规划
     */
    public static int minPathSum3(int[][] matrix) {
        int n = matrix.length;
        int m = matrix[0].length;
        int[][] dp = new int[n][m];
        dp[0][0] = matrix[0][0];
        for (int x = 1; x < n; ++x) {
            dp[x][0] = dp[x - 1][0] + matrix[x][0];
        }
        for (int y = 1; y < m; ++y) {
            dp[0][y] = dp[0][y - 1] + matrix[0][y];
        }
        for (int x = 1; x < n; ++x) {
            for (int y = 1; y < m; ++y) {
                dp[x][y] = Math.min(dp[x - 1][y], dp[x][y - 1]) + matrix[x][y];
            }
        }
        return dp[n - 1][m - 1];
    }

    /**
     * 动态规划 - 空间压缩
     * 如果当前的结果依赖 左上、上 的二维DP表，都可以压缩成一维，例如
     * dp[1][1]依赖于 左上dp[1][0] 上dp[0][1]
     * 可以优化为 dp[1]依赖 左上dp[0] 上dp[1]，更新dp[1]即可
     * 这种依赖方式，使用所有这样子的dp二维表
     */
    public static int minPathSum4(int[][] matrix) {
        int n = matrix.length;
        int m = matrix[0].length;
        int[] dp = new int[m];
        dp[0] = matrix[0][0];
        for (int y = 1; y < m; ++y) {
            dp[y] += dp[y - 1] + matrix[0][y];
        }
        for (int x = 1; x < n; ++x) {
            dp[0] += matrix[x][0];
            for (int y = 1; y < m; ++y) {
                dp[y] = Math.min(dp[y - 1], dp[y]) + matrix[x][y];
            }
        }
        return dp[m - 1];
    }

    // for test
    public static int[][] generateRandomMatrix(int rowSize, int colSize) {
        if (rowSize < 0 || colSize < 0) {
            return null;
        }
        int[][] result = new int[rowSize][colSize];
        for (int i = 0; i != result.length; i++) {
            for (int j = 0; j != result[0].length; j++) {
                result[i][j] = (int) (Math.random() * 100);
            }
        }
        return result;
    }

    // for test
    public static void printMatrix(int[][] matrix) {
        for (int i = 0; i != matrix.length; i++) {
            for (int j = 0; j != matrix[0].length; j++) {
                System.out.print(matrix[i][j] + " ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        int rowSize = 10;
        int colSize = 10;
        int[][] m = generateRandomMatrix(rowSize, colSize);
        System.out.println(minPathSum1(m));
        System.out.println(minPathSum2(m));
        System.out.println(minPathSum3(m));
        System.out.println(minPathSum4(m));
    }

}
